package com.hyb.algorithm.data.struct.list;

import java.util.HashSet;
import java.util.Set;

/**
 * @Author: huyanbing
 * @Date: 2021/8/14 10:58 上午
 * <p>
 * 142. 环形链表 II
 * <p>
 * https://leetcode-cn.com/problems/linked-list-cycle-ii/
 * <p>
 * 解决方法：https://leetcode.wang/leetcode-142-Linked-List-CycleII.html
 */
public class DetectCycle {


    public static void main(String[] args) {

        //head = [3,2,0,-4], pos = 1

        ListNode head = new ListNode(3);
        head.next = new ListNode(2);
        head.next.next = new ListNode(0);
        head.next.next.next = new ListNode(-4);

        head.next.next.next.next = head.next;

        DetectCycle exe = new DetectCycle();
        System.out.println(exe.detectCycle(head).val);
    }


    /**
     * 参考 https://leetcode.wang/leetcode-142-Linked-List-CycleII.html
     * <p>
     * n-x-y为fast 指针走过的路  起点位置为 n-y  所以 n-(n-x)=x 步到起点
     *
     * @param head
     * @return
     */
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        ListNode meet = null;
        while (fast != null) {
            if (fast.next == null) {
                return null;
            }
            slow = slow.next;
            fast = fast.next.next;
            //到达相遇点
            if (fast == slow) {
                meet = fast;
                while (head != meet) {
                    head = head.next;
                    meet = meet.next;
                }
                return head;
            }
        }
        return null;
    }



    public ListNode detectCycle2(ListNode head) {

        /**
         * 通过字典判断 是否包含重复节点 如果第一次就重复 直接开始节点
         */
        Set<ListNode> listNodeSet = new HashSet<>();

        while (head != null) {
            listNodeSet.add(head);
            head = head.next;
            if (listNodeSet.contains(head)) {
                return head;
            }
        }

        return null;

    }


}
